#define _CRT_SECURE_NO_WARNINGS

#include "BinaryTree.h"
#include "Queue.h"

BTNode* BTCreateNode(BTDataType data)
{
	BTNode* temp = malloc(sizeof(BTNode));
	if (!temp)
	{
		printf("Malloc failed.\n");
		exit(1);
	}
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
}

void BTPreOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	BTPreOrder(root->left);
	BTPreOrder(root->right);
}

void BTInOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BTInOrder(root->left);
	printf("%c ", root->data);
	BTInOrder(root->right);
}

void BTPostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BTPostOrder(root->left);
	BTPostOrder(root->right);
	printf("%c ", root->data);
}

//void BTSize(BTNode* root, int* size)
//{
//	if (!root)
//	{
//		return;
//	}
//	(*size)++;
//	BTSize(root->left, size);
//	BTSize(root->right, size);
//}

int BTSize(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	return 1 + BTSize(root->left) + BTSize(root->right);
}

int BTLeafSize(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	if (!root->left && !root->right)
	{
		return 1;
	}
	return BTLeafSize(root->left) + BTLeafSize(root->right);
}

int BTLevelSize(BTNode* root, int level)
{
	if (!root)
	{
		return 0;
	}
	if (level == 1 && root)
	{
		return 1;
	}
	level--;
	return BTLevelSize(root->left, level) + BTLevelSize(root->right, level);
}

int BTGetHeight(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	int left = BTGetHeight(root->left);
	int right = BTGetHeight(root->right);
	return 1 + ((left > right) ? left : right);
}

BTNode* BTFind(BTNode* root, BTDataType data)
{
	if (!root)
	{
		return NULL;
	}
	if (root->data == data)
	{
		return root;
	}
	BTNode* ret1 = BTFind(root->left, data);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BTFind(root->right, data);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}

void BTDestory(BTNode** root)
{
	if (!(*root))
	{
		return;
	}
	BTDestory(&(*root)->left);
	BTDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

void BTLevelOrder(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root);
	BTNode* temp = NULL;
	for (; !QueueIsEmpty(&queue);)
	{
		temp = QueuePop(&queue);
		printf("%c ", temp->data);
		if (temp->left)
		{
			QueuePush(&queue, temp->left);
		}
		if (temp->right)
		{
			QueuePush(&queue, temp->right);
		}
	}
}

bool BTIsComplete(BTNode* root)
{
	if (!root)
	{
		return true;
	}
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root);
	BTNode* temp = NULL;
	bool end = false;
	for (; !QueueIsEmpty(&queue);)
	{
		temp = QueuePop(&queue);
		if (temp->left)
		{
			if (end)
			{
				QueueDestory(&queue);
				return false;
			}
			QueuePush(&queue, temp->left);
		}
		else
		{
			end = true;
		}
		if (temp->right)
		{
			if (end)
			{
				QueueDestory(&queue);
				return false;
			}
			QueuePush(&queue, temp->right);
		}
		else
		{
			end = true;
		}
	}

	QueueDestory(&queue);
	return true;
}